Maximum independent sets on random regular graphs

Abstract: We determine the asymptotics of the independence number of the random d-regular graph for all d exceeding an absolute constant. The independence number is highly concentrated, with constant-order fluctuations around (a*n-c*log n) for explicit constants a(d) and c(d). Our proof rigorously confirms one-step replica symmetry breaking heuristics for this problem.

Mathematics

Audience: researchers in the topic

ICCM 2020